//
// Created by lenovo on 2024/8/11.
//

#ifndef BITREELIB_TREE_MUTITREE___MUTITREE___H
#define BITREELIB_TREE_MUTITREE___MUTITREE___H
#include <iostream>
#include <queue>

namespace TREE{
#define interface class
#define ABSTRACT_CLASS
#define abstract ABSTRACT_CLASS
    /**
     * @tparam T
     *
     * @req
     * Node应当有两种类型:
     * 1.紧凑的
     *  紧凑的Tree不允许有child为null,即使有空值也应当移动后续的来填充
     * 2.允许空值的
     *  child允许为null,在实际应用中可能更加广泛
     *
     * @solution
     * 通过setChild即可完成添加孩子或者设置空值的需求
     * 而添加了pop功能,移除某位置的值后,将后续元素向前填充
     *
     * @par
     * width,capacity都是int而非size_t
     * 为了能在特殊情况下返还-1这一个信号
     */
    template <typename T>
    interface Node{
    public:
        virtual Node*   getChild    (int n) = 0 ;
        virtual Node*   parent      () = 0 ;
        virtual void    pop         (int n) = 0 ;
        virtual void    setChild    (T data , int n) = 0 ;
        virtual void    setChild    (Node<T>* node , int n) = 0 ;
        virtual int     width       ()  const = 0 ;
        virtual int     capacity    ()  const = 0 ;
        virtual T       data        () = 0 ;
        using   value_type = T;
    };



    template <typename T , typename _Visit>
    bool PreOrder(Node<T>* node , _Visit&& __visit){
        //node为空
        if (not node){
            if (not __visit(node)){
                return false ;
            }
            return true ;
        }
        //node存在
        if (not __visit(node))
            return false ;

        for (size_t i = 0 ; i < node->width() ; i ++){
            if (not PreOrder(node->getChild(i),__visit))
                return false ;
        }
        return true ;
    }

    template <typename T, typename _Visit>
    bool PostOrder(Node<T>* node, _Visit&& __visit) {
        if (not node) {
            return __visit(node);
        }

        for (size_t i = 0; i < node->width(); ++i) {
            if (not PostOrder(node->getChild(i), __visit)) {
                return false;
            }
        }

        return __visit(node);
    }

    template <typename T, typename _Visit>
    bool LevelOrder(Node<T>* root, _Visit&& __visit) {
        if (!root) {
            return !__visit(root);
        }

        std::queue<Node<T>*> q;
        q.push(root);

        while (!q.empty()) {
            Node<T>* node = q.front();
            if (!__visit(node)) {
                return false;
            }
            q.pop();



            if (node != nullptr){
                for (size_t i = 0; i < node->width(); ++i) {
                    Node<T>* child = node->getChild(i);
                    q.push(child);
                }
            }
        }

        return true;
    }
}
#endif //BITREELIB_TREE_MUTITREE___MUTITREE___H
